/**
 * 
 */
package leetCode;

import java.util.Arrays;

/**
 * @author zhong
 *
 */
public class TwoCityScheduling {
	public int twoCitySchedCost(int[][] costs) {
		int[][] sum = new int[costs.length][2];
		for (int i = 0; i < sum.length; i++) {
			sum[i][0] = costs[i][0] - costs[i][1];
			sum[i][1] = i;
		}
		Arrays.sort(sum, (a, b) -> a[0] - b[0]);
		int N = costs.length / 2;
		int res = 0;
		int i = 0;
		for (; i < N; i++) {
			int j = sum[i][1];
			res += costs[j][0];
		}
		for (; i < sum.length; i++) {
			int j = sum[i][1];
			res += costs[j][1];

		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
